package binarytree

func findTarget(root *TreeNode, k int) bool {
	if root == nil {
		return false
	}

	q := []*TreeNode{root}
	nums := []int{}

	for len(q) > 0 {
		levelLen := len(q)
		for i := 0; i < levelLen; i++ {
			nums = append(nums, q[i].Val)
			if q[i].Left != nil {
				q = append(q, q[i].Left)
			}
			if q[i].Right != nil {
				q = append(q, q[i].Right)
			}
		}

		q = q[levelLen:]
	}

	hash := map[int]int{}

	for i := 0; i < len(nums); i++ {
		if _, ok := hash[nums[i]]; ok {
			return true
		}

		hash[k-nums[i]] = nums[i]
	}

	return true

}
